        -:    0:Source:/usr/include/c++/9/bits/stl_heap.h
        -:    1:// Heap implementation -*- C++ -*-
        -:    2:
        -:    3:// Copyright (C) 2001-2019 Free Software Foundation, Inc.
        -:    4://
        -:    5:// This file is part of the GNU ISO C++ Library.  This library is free
        -:    6:// software; you can redistribute it and/or modify it under the
        -:    7:// terms of the GNU General Public License as published by the
        -:    8:// Free Software Foundation; either version 3, or (at your option)
        -:    9:// any later version.
        -:   10:
        -:   11:// This library is distributed in the hope that it will be useful,
        -:   12:// but WITHOUT ANY WARRANTY; without even the implied warranty of
        -:   13:// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        -:   14:// GNU General Public License for more details.
        -:   15:
        -:   16:// Under Section 7 of GPL version 3, you are granted additional
        -:   17:// permissions described in the GCC Runtime Library Exception, version
        -:   18:// 3.1, as published by the Free Software Foundation.
        -:   19:
        -:   20:// You should have received a copy of the GNU General Public License and
        -:   21:// a copy of the GCC Runtime Library Exception along with this program;
        -:   22:// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
        -:   23:// <http://www.gnu.org/licenses/>.
        -:   24:
        -:   25:/*
        -:   26: *
        -:   27: * Copyright (c) 1994
        -:   28: * Hewlett-Packard Company
        -:   29: *
        -:   30: * Permission to use, copy, modify, distribute and sell this software
        -:   31: * and its documentation for any purpose is hereby granted without fee,
        -:   32: * provided that the above copyright notice appear in all copies and
        -:   33: * that both that copyright notice and this permission notice appear
        -:   34: * in supporting documentation.  Hewlett-Packard Company makes no
        -:   35: * representations about the suitability of this software for any
        -:   36: * purpose.  It is provided "as is" without express or implied warranty.
        -:   37: *
        -:   38: * Copyright (c) 1997
        -:   39: * Silicon Graphics Computer Systems, Inc.
        -:   40: *
        -:   41: * Permission to use, copy, modify, distribute and sell this software
        -:   42: * and its documentation for any purpose is hereby granted without fee,
        -:   43: * provided that the above copyright notice appear in all copies and
        -:   44: * that both that copyright notice and this permission notice appear
        -:   45: * in supporting documentation.  Silicon Graphics makes no
        -:   46: * representations about the suitability of this software for any
        -:   47: * purpose.  It is provided "as is" without express or implied warranty.
        -:   48: */
        -:   49:
        -:   50:/** @file bits/stl_heap.h
        -:   51: *  This is an internal header file, included by other library headers.
        -:   52: *  Do not attempt to use it directly. @headername{queue}
        -:   53: */
        -:   54:
        -:   55:#ifndef _STL_HEAP_H
        -:   56:#define _STL_HEAP_H 1
        -:   57:
        -:   58:#include <debug/debug.h>
        -:   59:#include <bits/move.h>
        -:   60:#include <bits/predefined_ops.h>
        -:   61:
        -:   62:namespace std _GLIBCXX_VISIBILITY(default)
        -:   63:{
        -:   64:_GLIBCXX_BEGIN_NAMESPACE_VERSION
        -:   65:
        -:   66:  /**
        -:   67:   * @defgroup heap_algorithms Heap
        -:   68:   * @ingroup sorting_algorithms
        -:   69:   */
        -:   70:
        -:   71:  template<typename _RandomAccessIterator, typename _Distance,
        -:   72:	   typename _Compare>
        -:   73:    _Distance
        -:   74:    __is_heap_until(_RandomAccessIterator __first, _Distance __n,
        -:   75:		    _Compare& __comp)
        -:   76:    {
        -:   77:      _Distance __parent = 0;
        -:   78:      for (_Distance __child = 1; __child < __n; ++__child)
        -:   79:	{
        -:   80:	  if (__comp(__first + __parent, __first + __child))
        -:   81:	    return __child;
        -:   82:	  if ((__child & 1) == 0)
        -:   83:	    ++__parent;
        -:   84:	}
        -:   85:      return __n;
        -:   86:    }
        -:   87:
        -:   88:  // __is_heap, a predicate testing whether or not a range is a heap.
        -:   89:  // This function is an extension, not part of the C++ standard.
        -:   90:  template<typename _RandomAccessIterator, typename _Distance>
        -:   91:    inline bool
        -:   92:    __is_heap(_RandomAccessIterator __first, _Distance __n)
        -:   93:    {
        -:   94:      __gnu_cxx::__ops::_Iter_less_iter __comp;
        -:   95:      return std::__is_heap_until(__first, __n, __comp) == __n;
        -:   96:    }
        -:   97:
        -:   98:  template<typename _RandomAccessIterator, typename _Compare,
        -:   99:	   typename _Distance>
        -:  100:    inline bool
        -:  101:    __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
        -:  102:    {
        -:  103:      typedef __decltype(__comp) _Cmp;
        -:  104:      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
        -:  105:      return std::__is_heap_until(__first, __n, __cmp) == __n;
        -:  106:    }
        -:  107:
        -:  108:  template<typename _RandomAccessIterator>
        -:  109:    inline bool
        -:  110:    __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
        -:  111:    { return std::__is_heap(__first, std::distance(__first, __last)); }
        -:  112:
        -:  113:  template<typename _RandomAccessIterator, typename _Compare>
        -:  114:    inline bool
        -:  115:    __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        -:  116:	      _Compare __comp)
        -:  117:    {
        -:  118:      return std::__is_heap(__first, _GLIBCXX_MOVE(__comp),
        -:  119:			    std::distance(__first, __last));
        -:  120:    }
        -:  121:
        -:  122:  // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
        -:  123:  // + is_heap and is_heap_until in C++0x.
        -:  124:
        -:  125:  template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
        -:  126:	   typename _Compare>
        -:  127:    void
        -:  128:    __push_heap(_RandomAccessIterator __first,
        -:  129:		_Distance __holeIndex, _Distance __topIndex, _Tp __value,
        -:  130:		_Compare& __comp)
        -:  131:    {
        -:  132:      _Distance __parent = (__holeIndex - 1) / 2;
        -:  133:      while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
        -:  134:	{
        -:  135:	  *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
        -:  136:	  __holeIndex = __parent;
        -:  137:	  __parent = (__holeIndex - 1) / 2;
        -:  138:	}
        -:  139:      *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
        -:  140:    }
        -:  141:
        -:  142:  /**
        -:  143:   *  @brief  Push an element onto a heap.
        -:  144:   *  @param  __first  Start of heap.
        -:  145:   *  @param  __last   End of heap + element.
        -:  146:   *  @ingroup heap_algorithms
        -:  147:   *
        -:  148:   *  This operation pushes the element at last-1 onto the valid heap
        -:  149:   *  over the range [__first,__last-1).  After completion,
        -:  150:   *  [__first,__last) is a valid heap.
        -:  151:  */
        -:  152:  template<typename _RandomAccessIterator>
        -:  153:    inline void
        -:  154:    push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
        -:  155:    {
        -:  156:      typedef typename iterator_traits<_RandomAccessIterator>::value_type
        -:  157:	  _ValueType;
        -:  158:      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
        -:  159:	  _DistanceType;
        -:  160:
        -:  161:      // concept requirements
        -:  162:      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        -:  163:	    _RandomAccessIterator>)
        -:  164:      __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
        -:  165:      __glibcxx_requires_valid_range(__first, __last);
        -:  166:      __glibcxx_requires_irreflexive(__first, __last);
        -:  167:      __glibcxx_requires_heap(__first, __last - 1);
        -:  168:
        -:  169:      __gnu_cxx::__ops::_Iter_less_val __comp;
        -:  170:      _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
        -:  171:      std::__push_heap(__first, _DistanceType((__last - __first) - 1),
        -:  172:		       _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
        -:  173:    }
        -:  174:
        -:  175:  /**
        -:  176:   *  @brief  Push an element onto a heap using comparison functor.
        -:  177:   *  @param  __first  Start of heap.
        -:  178:   *  @param  __last   End of heap + element.
        -:  179:   *  @param  __comp   Comparison functor.
        -:  180:   *  @ingroup heap_algorithms
        -:  181:   *
        -:  182:   *  This operation pushes the element at __last-1 onto the valid
        -:  183:   *  heap over the range [__first,__last-1).  After completion,
        -:  184:   *  [__first,__last) is a valid heap.  Compare operations are
        -:  185:   *  performed using comp.
        -:  186:  */
        -:  187:  template<typename _RandomAccessIterator, typename _Compare>
        -:  188:    inline void
        -:  189:    push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        -:  190:	      _Compare __comp)
        -:  191:    {
        -:  192:      typedef typename iterator_traits<_RandomAccessIterator>::value_type
        -:  193:	  _ValueType;
        -:  194:      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
        -:  195:	  _DistanceType;
        -:  196:
        -:  197:      // concept requirements
        -:  198:      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        -:  199:	    _RandomAccessIterator>)
        -:  200:      __glibcxx_requires_valid_range(__first, __last);
        -:  201:      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
        -:  202:      __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
        -:  203:
        -:  204:      __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
        -:  205:	__cmp(_GLIBCXX_MOVE(__comp));
        -:  206:      _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
        -:  207:      std::__push_heap(__first, _DistanceType((__last - __first) - 1),
        -:  208:		       _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
        -:  209:    }
        -:  210:
        -:  211:  template<typename _RandomAccessIterator, typename _Distance,
        -:  212:	   typename _Tp, typename _Compare>
        -:  213:    void
    #####:  214:    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
        -:  215:		  _Distance __len, _Tp __value, _Compare __comp)
        -:  216:    {
        -:  217:      const _Distance __topIndex = __holeIndex;
        -:  218:      _Distance __secondChild = __holeIndex;
    #####:  219:      while (__secondChild < (__len - 1) / 2)
        -:  220:	{
    #####:  221:	  __secondChild = 2 * (__secondChild + 1);
    #####:  222:	  if (__comp(__first + __secondChild,
    #####:  223:		     __first + (__secondChild - 1)))
    #####:  224:	    __secondChild--;
    #####:  225:	  *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
        -:  226:	  __holeIndex = __secondChild;
        -:  227:	}
    #####:  228:      if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
        -:  229:	{
    #####:  230:	  __secondChild = 2 * (__secondChild + 1);
    #####:  231:	  *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
        -:  232:						     + (__secondChild - 1)));
    #####:  233:	  __holeIndex = __secondChild - 1;
        -:  234:	}
        -:  235:      __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
    #####:  236:	__cmp(_GLIBCXX_MOVE(__comp));
    #####:  237:      std::__push_heap(__first, __holeIndex, __topIndex,
    #####:  238:		       _GLIBCXX_MOVE(__value), __cmp);
    #####:  239:    }
------------------
_ZSt13__adjust_heapIPN13CaptureButton10ButtonTypeElS1_N9__gnu_cxx5__ops15_Iter_comp_iterIZN13ConfigHandler10getButtonsEvEUlS1_S1_E2_EEEvT_T0_SA_T1_T2_:
    #####:  214:    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
        -:  215:		  _Distance __len, _Tp __value, _Compare __comp)
        -:  216:    {
        -:  217:      const _Distance __topIndex = __holeIndex;
        -:  218:      _Distance __secondChild = __holeIndex;
    #####:  219:      while (__secondChild < (__len - 1) / 2)
        -:  220:	{
    #####:  221:	  __secondChild = 2 * (__secondChild + 1);
    #####:  222:	  if (__comp(__first + __secondChild,
    #####:  223:		     __first + (__secondChild - 1)))
    #####:  224:	    __secondChild--;
    #####:  225:	  *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
        -:  226:	  __holeIndex = __secondChild;
        -:  227:	}
    #####:  228:      if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
        -:  229:	{
    #####:  230:	  __secondChild = 2 * (__secondChild + 1);
    #####:  231:	  *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
        -:  232:						     + (__secondChild - 1)));
    #####:  233:	  __holeIndex = __secondChild - 1;
        -:  234:	}
        -:  235:      __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
    #####:  236:	__cmp(_GLIBCXX_MOVE(__comp));
    #####:  237:      std::__push_heap(__first, __holeIndex, __topIndex,
    #####:  238:		       _GLIBCXX_MOVE(__value), __cmp);
    #####:  239:    }
------------------
_ZSt13__adjust_heapIPN13CaptureButton10ButtonTypeElS1_N9__gnu_cxx5__ops15_Iter_comp_iterIZN14ButtonListView19updateActiveButtonsEP15QListWidgetItemEUlS1_S1_E_EEEvT_T0_SC_T1_T2_:
    #####:  214:    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
        -:  215:		  _Distance __len, _Tp __value, _Compare __comp)
        -:  216:    {
        -:  217:      const _Distance __topIndex = __holeIndex;
        -:  218:      _Distance __secondChild = __holeIndex;
    #####:  219:      while (__secondChild < (__len - 1) / 2)
        -:  220:	{
    #####:  221:	  __secondChild = 2 * (__secondChild + 1);
    #####:  222:	  if (__comp(__first + __secondChild,
    #####:  223:		     __first + (__secondChild - 1)))
    #####:  224:	    __secondChild--;
    #####:  225:	  *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
        -:  226:	  __holeIndex = __secondChild;
        -:  227:	}
    #####:  228:      if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
        -:  229:	{
    #####:  230:	  __secondChild = 2 * (__secondChild + 1);
    #####:  231:	  *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
        -:  232:						     + (__secondChild - 1)));
    #####:  233:	  __holeIndex = __secondChild - 1;
        -:  234:	}
        -:  235:      __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
    #####:  236:	__cmp(_GLIBCXX_MOVE(__comp));
    #####:  237:      std::__push_heap(__first, __holeIndex, __topIndex,
    #####:  238:		       _GLIBCXX_MOVE(__value), __cmp);
    #####:  239:    }
------------------
        -:  240:
        -:  241:  template<typename _RandomAccessIterator, typename _Compare>
        -:  242:    inline void
        -:  243:    __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        -:  244:	       _RandomAccessIterator __result, _Compare& __comp)
        -:  245:    {
        -:  246:      typedef typename iterator_traits<_RandomAccessIterator>::value_type
        -:  247:	_ValueType;
        -:  248:      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
        -:  249:	_DistanceType;
        -:  250:
        -:  251:      _ValueType __value = _GLIBCXX_MOVE(*__result);
        -:  252:      *__result = _GLIBCXX_MOVE(*__first);
        -:  253:      std::__adjust_heap(__first, _DistanceType(0),
        -:  254:			 _DistanceType(__last - __first),
        -:  255:			 _GLIBCXX_MOVE(__value), __comp);
        -:  256:    }
        -:  257:
        -:  258:  /**
        -:  259:   *  @brief  Pop an element off a heap.
        -:  260:   *  @param  __first  Start of heap.
        -:  261:   *  @param  __last   End of heap.
        -:  262:   *  @pre    [__first, __last) is a valid, non-empty range.
        -:  263:   *  @ingroup heap_algorithms
        -:  264:   *
        -:  265:   *  This operation pops the top of the heap.  The elements __first
        -:  266:   *  and __last-1 are swapped and [__first,__last-1) is made into a
        -:  267:   *  heap.
        -:  268:  */
        -:  269:  template<typename _RandomAccessIterator>
        -:  270:    inline void
        -:  271:    pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
        -:  272:    {
        -:  273:      // concept requirements
        -:  274:      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        -:  275:	    _RandomAccessIterator>)
        -:  276:      __glibcxx_function_requires(_LessThanComparableConcept<
        -:  277:	typename iterator_traits<_RandomAccessIterator>::value_type>)
        -:  278:      __glibcxx_requires_non_empty_range(__first, __last);
        -:  279:      __glibcxx_requires_valid_range(__first, __last);
        -:  280:      __glibcxx_requires_irreflexive(__first, __last);
        -:  281:      __glibcxx_requires_heap(__first, __last);
        -:  282:
        -:  283:      if (__last - __first > 1)
        -:  284:	{
        -:  285:	  --__last;
        -:  286:	  __gnu_cxx::__ops::_Iter_less_iter __comp;
        -:  287:	  std::__pop_heap(__first, __last, __last, __comp);
        -:  288:	}
        -:  289:    }
        -:  290:
        -:  291:  /**
        -:  292:   *  @brief  Pop an element off a heap using comparison functor.
        -:  293:   *  @param  __first  Start of heap.
        -:  294:   *  @param  __last   End of heap.
        -:  295:   *  @param  __comp   Comparison functor to use.
        -:  296:   *  @ingroup heap_algorithms
        -:  297:   *
        -:  298:   *  This operation pops the top of the heap.  The elements __first
        -:  299:   *  and __last-1 are swapped and [__first,__last-1) is made into a
        -:  300:   *  heap.  Comparisons are made using comp.
        -:  301:  */
        -:  302:  template<typename _RandomAccessIterator, typename _Compare>
        -:  303:    inline void
        -:  304:    pop_heap(_RandomAccessIterator __first,
        -:  305:	     _RandomAccessIterator __last, _Compare __comp)
        -:  306:    {
        -:  307:      // concept requirements
        -:  308:      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        -:  309:	    _RandomAccessIterator>)
        -:  310:      __glibcxx_requires_valid_range(__first, __last);
        -:  311:      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
        -:  312:      __glibcxx_requires_non_empty_range(__first, __last);
        -:  313:      __glibcxx_requires_heap_pred(__first, __last, __comp);
        -:  314:
        -:  315:      if (__last - __first > 1)
        -:  316:	{
        -:  317:	  typedef __decltype(__comp) _Cmp;
        -:  318:	  __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
        -:  319:	  --__last;
        -:  320:	  std::__pop_heap(__first, __last, __last, __cmp);
        -:  321:	}
        -:  322:    }
        -:  323:
        -:  324:  template<typename _RandomAccessIterator, typename _Compare>
        -:  325:    void
        -:  326:    __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        -:  327:		_Compare& __comp)
        -:  328:    {
        -:  329:      typedef typename iterator_traits<_RandomAccessIterator>::value_type
        -:  330:	  _ValueType;
        -:  331:      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
        -:  332:	  _DistanceType;
        -:  333:
        -:  334:      if (__last - __first < 2)
        -:  335:	return;
        -:  336:
        -:  337:      const _DistanceType __len = __last - __first;
        -:  338:      _DistanceType __parent = (__len - 2) / 2;
        -:  339:      while (true)
        -:  340:	{
        -:  341:	  _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
        -:  342:	  std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
        -:  343:			     __comp);
        -:  344:	  if (__parent == 0)
        -:  345:	    return;
        -:  346:	  __parent--;
        -:  347:	}
        -:  348:    }
        -:  349:  
        -:  350:  /**
        -:  351:   *  @brief  Construct a heap over a range.
        -:  352:   *  @param  __first  Start of heap.
        -:  353:   *  @param  __last   End of heap.
        -:  354:   *  @ingroup heap_algorithms
        -:  355:   *
        -:  356:   *  This operation makes the elements in [__first,__last) into a heap.
        -:  357:  */
        -:  358:  template<typename _RandomAccessIterator>
        -:  359:    inline void
        -:  360:    make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
        -:  361:    {
        -:  362:      // concept requirements
        -:  363:      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        -:  364:	    _RandomAccessIterator>)
        -:  365:      __glibcxx_function_requires(_LessThanComparableConcept<
        -:  366:	    typename iterator_traits<_RandomAccessIterator>::value_type>)
        -:  367:      __glibcxx_requires_valid_range(__first, __last);
        -:  368:      __glibcxx_requires_irreflexive(__first, __last);
        -:  369:
        -:  370:      __gnu_cxx::__ops::_Iter_less_iter __comp;
        -:  371:      std::__make_heap(__first, __last, __comp);
        -:  372:    }
        -:  373:
        -:  374:  /**
        -:  375:   *  @brief  Construct a heap over a range using comparison functor.
        -:  376:   *  @param  __first  Start of heap.
        -:  377:   *  @param  __last   End of heap.
        -:  378:   *  @param  __comp   Comparison functor to use.
        -:  379:   *  @ingroup heap_algorithms
        -:  380:   *
        -:  381:   *  This operation makes the elements in [__first,__last) into a heap.
        -:  382:   *  Comparisons are made using __comp.
        -:  383:  */
        -:  384:  template<typename _RandomAccessIterator, typename _Compare>
        -:  385:    inline void
        -:  386:    make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        -:  387:	      _Compare __comp)
        -:  388:    {
        -:  389:      // concept requirements
        -:  390:      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        -:  391:	    _RandomAccessIterator>)
        -:  392:      __glibcxx_requires_valid_range(__first, __last);
        -:  393:      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
        -:  394:
        -:  395:      typedef __decltype(__comp) _Cmp;
        -:  396:      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
        -:  397:      std::__make_heap(__first, __last, __cmp);
        -:  398:    }
        -:  399:
        -:  400:  template<typename _RandomAccessIterator, typename _Compare>
        -:  401:    void
        -:  402:    __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        -:  403:		_Compare& __comp)
        -:  404:    {
        -:  405:      while (__last - __first > 1)
        -:  406:	{
        -:  407:	  --__last;
        -:  408:	  std::__pop_heap(__first, __last, __last, __comp);
        -:  409:	}
        -:  410:    }
        -:  411:
        -:  412:  /**
        -:  413:   *  @brief  Sort a heap.
        -:  414:   *  @param  __first  Start of heap.
        -:  415:   *  @param  __last   End of heap.
        -:  416:   *  @ingroup heap_algorithms
        -:  417:   *
        -:  418:   *  This operation sorts the valid heap in the range [__first,__last).
        -:  419:  */
        -:  420:  template<typename _RandomAccessIterator>
        -:  421:    inline void
        -:  422:    sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
        -:  423:    {
        -:  424:      // concept requirements
        -:  425:      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        -:  426:	    _RandomAccessIterator>)
        -:  427:      __glibcxx_function_requires(_LessThanComparableConcept<
        -:  428:	    typename iterator_traits<_RandomAccessIterator>::value_type>)
        -:  429:      __glibcxx_requires_valid_range(__first, __last);
        -:  430:      __glibcxx_requires_irreflexive(__first, __last);
        -:  431:      __glibcxx_requires_heap(__first, __last);
        -:  432:
        -:  433:      __gnu_cxx::__ops::_Iter_less_iter __comp;
        -:  434:      std::__sort_heap(__first, __last, __comp);
        -:  435:    }
        -:  436:
        -:  437:  /**
        -:  438:   *  @brief  Sort a heap using comparison functor.
        -:  439:   *  @param  __first  Start of heap.
        -:  440:   *  @param  __last   End of heap.
        -:  441:   *  @param  __comp   Comparison functor to use.
        -:  442:   *  @ingroup heap_algorithms
        -:  443:   *
        -:  444:   *  This operation sorts the valid heap in the range [__first,__last).
        -:  445:   *  Comparisons are made using __comp.
        -:  446:  */
        -:  447:  template<typename _RandomAccessIterator, typename _Compare>
        -:  448:    inline void
        -:  449:    sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        -:  450:	      _Compare __comp)
        -:  451:    {
        -:  452:      // concept requirements
        -:  453:      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        -:  454:	    _RandomAccessIterator>)
        -:  455:      __glibcxx_requires_valid_range(__first, __last);
        -:  456:      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
        -:  457:      __glibcxx_requires_heap_pred(__first, __last, __comp);
        -:  458:
        -:  459:      typedef __decltype(__comp) _Cmp;
        -:  460:      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
        -:  461:      std::__sort_heap(__first, __last, __cmp);
        -:  462:    }
        -:  463:
        -:  464:#if __cplusplus >= 201103L
        -:  465:  /**
        -:  466:   *  @brief  Search the end of a heap.
        -:  467:   *  @param  __first  Start of range.
        -:  468:   *  @param  __last   End of range.
        -:  469:   *  @return  An iterator pointing to the first element not in the heap.
        -:  470:   *  @ingroup heap_algorithms
        -:  471:   *
        -:  472:   *  This operation returns the last iterator i in [__first, __last) for which
        -:  473:   *  the range [__first, i) is a heap.
        -:  474:  */
        -:  475:  template<typename _RandomAccessIterator>
        -:  476:    inline _RandomAccessIterator
        -:  477:    is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
        -:  478:    {
        -:  479:      // concept requirements
        -:  480:      __glibcxx_function_requires(_RandomAccessIteratorConcept<
        -:  481:	    _RandomAccessIterator>)
        -:  482:      __glibcxx_function_requires(_LessThanComparableConcept<
        -:  483:	    typename iterator_traits<_RandomAccessIterator>::value_type>)
        -:  484:      __glibcxx_requires_valid_range(__first, __last);
        -:  485:      __glibcxx_requires_irreflexive(__first, __last);
        -:  486:
        -:  487:      __gnu_cxx::__ops::_Iter_less_iter __comp;
        -:  488:      return __first + 
        -:  489:	std::__is_heap_until(__first, std::distance(__first, __last), __comp);
        -:  490:    }
        -:  491:
        -:  492:  /**
        -:  493:   *  @brief  Search the end of a heap using comparison functor.
        -:  494:   *  @param  __first  Start of range.
        -:  495:   *  @param  __last   End of range.
        -:  496:   *  @param  __comp   Comparison functor to use.
        -:  497:   *  @return  An iterator pointing to the first element not in the heap.
        -:  498:   *  @ingroup heap_algorithms
        -:  499:   *
        -:  500:   *  This operation returns the last iterator i in [__first, __last) for which
        -:  501:   *  the range [__first, i) is a heap.  Comparisons are made using __comp.
        -:  502:  */
        -:  503:  template<typename _RandomAccessIterator, typename _Compare>
        -:  504:    inline _RandomAccessIterator
        -:  505:    is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
        -:  506:		  _Compare __comp)
        -:  507:    {
        -:  508:      // concept requirements
        -:  509:      __glibcxx_function_requires(_RandomAccessIteratorConcept<
        -:  510:	    _RandomAccessIterator>)
        -:  511:      __glibcxx_requires_valid_range(__first, __last);
        -:  512:      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
        -:  513:
        -:  514:      typedef __decltype(__comp) _Cmp;
        -:  515:      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
        -:  516:      return __first
        -:  517:	+ std::__is_heap_until(__first, std::distance(__first, __last), __cmp);
        -:  518:    }
        -:  519:
        -:  520:  /**
        -:  521:   *  @brief  Determines whether a range is a heap.
        -:  522:   *  @param  __first  Start of range.
        -:  523:   *  @param  __last   End of range.
        -:  524:   *  @return  True if range is a heap, false otherwise.
        -:  525:   *  @ingroup heap_algorithms
        -:  526:  */
        -:  527:  template<typename _RandomAccessIterator>
        -:  528:    inline bool
        -:  529:    is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
        -:  530:    { return std::is_heap_until(__first, __last) == __last; }
        -:  531:
        -:  532:  /**
        -:  533:   *  @brief  Determines whether a range is a heap using comparison functor.
        -:  534:   *  @param  __first  Start of range.
        -:  535:   *  @param  __last   End of range.
        -:  536:   *  @param  __comp   Comparison functor to use.
        -:  537:   *  @return  True if range is a heap, false otherwise.
        -:  538:   *  @ingroup heap_algorithms
        -:  539:  */
        -:  540:  template<typename _RandomAccessIterator, typename _Compare>
        -:  541:    inline bool
        -:  542:    is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        -:  543:	    _Compare __comp)
        -:  544:    {
        -:  545:      // concept requirements
        -:  546:      __glibcxx_function_requires(_RandomAccessIteratorConcept<
        -:  547:	    _RandomAccessIterator>)
        -:  548:      __glibcxx_requires_valid_range(__first, __last);
        -:  549:      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
        -:  550:
        -:  551:      const auto __dist = std::distance(__first, __last);
        -:  552:      typedef __decltype(__comp) _Cmp;
        -:  553:      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
        -:  554:      return std::__is_heap_until(__first, __dist, __cmp) == __dist;
        -:  555:    }
        -:  556:#endif
        -:  557:
        -:  558:_GLIBCXX_END_NAMESPACE_VERSION
        -:  559:} // namespace
        -:  560:
        -:  561:#endif /* _STL_HEAP_H */
